package cxydmmszl.chapter08.t138;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

/**
 * <li style="color: red;">Prob</li>
 * 求最短通路值
 * <li style="color: red;">Desc</li>
 *
 * <li style="color: red;">Link</li> CD38
 *
 * @author habitplus
 * @since 2021-09-07 09:14
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] ss = bf.readLine().split(" ");
        int n = Integer.parseInt(ss[0]);
        int m = Integer.parseInt(ss[1]);
        char[][] map = new char[n][m];
        String s;
        for (int i = 0; i < n; i++) {
            s = bf.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = s.charAt(j);
            }
        }
        bf.close();

        int steps = minPathValue(map);
        System.out.println(steps);
    }

    private static int minPathValue(char[][] map) {
        if (map == null || map.length == 0 || map[0].length == 0) {
            return 0;
        }

        /*
            BFS
         */
        int n = map.length, m = map[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] vis = new boolean[n][m];
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int step = 0;
        int x, y;
        int[] d;
        queue.offer(new int[]{0, 0});
        vis[0][0] = true;

        while (!queue.isEmpty()) {
            step++;
            for (int i = queue.size(); i > 0; i--) {
                d = queue.poll();

                // 到达指定的点
                if (d[0] == n - 1 && d[1] == m - 1) {
                    return step;
                }

                for (int[] inc : dir) {
                    x = d[0] + inc[0];
                    y = d[1] + inc[1];
                    // 不越界 && 没有访问过 && 可达(map[i][j] = '1')
                    if (0 <= x && x < n && 0 <= y && y < m && !vis[x][y] && map[x][y] == '1') {
                        queue.offer(new int[]{x, y});
                        vis[x][y] = true; // 标记该点已经被访问了
                    }
                }
            }
        }

        return -1;
    }
}
